Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery

摘要

We propose a new iteratively reweighted least squares (IRLS) algorithm forthe recovery of a matrix $X \in \mathbb{C}^{d_1\times d_2}$ of rank $r\ll\min(d_1,d_2)$ from incomplete linear observations, solving a sequence oflow complexity linear problems. The easily implementable algorithm, which wecall harmonic mean iteratively reweighted least squares (HM-IRLS), optimizes anon-convex Schatten-$p$ quasi-norm penalization to promote low-rankness andcarries three major strengths, in particular for the matrix completion setting.First, the algorithm converges globally to the low-rank matrix for relevant,interesting cases, for which any other (non-)convex state-of-the-artoptimization approach fails the recovery. Secondly, HM-IRLS exhibits anempirical recovery probability close to $100\%$ even for a number ofmeasurements very close to the theoretical lower bound $r (d_1 +d_2 -r)$, i.e.,already for significantly fewer linear observations than any other tractableapproach in the literature. Thirdly, HM-IRLS exhibits a locally superlinearrate of convergence (of order $2-p$) if the linear observations fulfill asuitable null space property. While for the first two properties we have so faronly strong empirical evidence, we prove the third property as our maintheoretical result.